﻿using System;
using System.Collections.Generic;
using System.Text;

namespace MinimumSpanningTrees
{
    public class PrimMST
    {
        //private Edge[] edgeTo;//距离树最近的边
        //private double[] distTo;//distTo[w]=edgeTo[w].weight()
        //private bool[] marked;//如果 v 在树中则为 true
        //public IndexMinPQ<double> pq;//有效的横切边

        //public PrimMST(EdgeWeightedGraph G)
        //{
        //    edgeTo = new Edge[G.V()];
        //    distTo = new double[G.V()];
        //    marked = new bool[G.V()];

        //    for (int v = 0; v < G.V(); v++)
        //    {
        //        distTo[v] = Double.MaxValue;
        //    }

        //    pq = new IndexMinPQ<double>(G.V());

        //    distTo[0] = 0.0;
        //    pq.Insert(0,0.0); //用顶点 0 和权重 0 初始化 pq
        //    while (pq.Count > 0)
        //    {
        //        Visit(G,pq.DelMin());//将最近的顶点添加到树中
        //    }
        //}

        //private void Visit(EdgeWeightedGraph G, int v)
        //{
        //    //将顶点 v 添加到树中，更新数据
        //    marked[v] = true;
        //    foreach (Edge e in G.Adj(v))
        //    {
        //        int w = e.Other(v);

        //        if (marked[w])
        //            continue;

        //        if (e.Weight() < distTo[w])
        //        {
        //            edgeTo[w] = e;
        //            distTo[w] = e.Weight();

        //            if (pq.Contains(w))
        //                pq.Change(w, distTo[w]);
        //            else
        //                pq.Insert(w,distTo[w]);
        //        }
        //    }
        //}
    }
}
